pub fn dp_rec_mc(amount: u32) -> u32 {
    let coins = vec![1, 2, 5, 10, 20, 30, 50, 100];
    let mut used_coins = 0;
    let mut remain = amount;

    for &coin in coins.iter().rev() {
        if remain >= coin {
            used_coins += remain / coin;
            remain %= coin;
        }
    }

    used_coins
}

// pub fn dp_rec_mc(amount: u32) -> u32 {
//     let coins = vec![1, 2, 5, 10, 20,30,50,100];
//     let mut dp = vec![0; amount as usize + 1];
//     dp[0] = 0;

//     for i in 1..=amount as usize {
//         let mut min_coins = u32::MAX;
//         for &coin in coins.iter() {
//             if i >= coin as usize {
//                 min_coins = min_coins.min(dp[i - coin as usize]);
//             }
//         }
//         dp[i] = min_coins + 1;
//     }

//     dp[amount as usize]
// }
